import os, sys
sys.path.insert(0, os.path.abspath(os.path.join(os.path.dirname(__file__), '..')))
from lList import CLinkList
# Note that the header node is empty; it's best to eliminate the header node, which will make the code logic simpler
def solve_joseph(L, A, n, m):
    # Initialize counter for counting steps in the inner loop
    cnt = 0
    
    # Start pointers p and pre at the head of list L
    p = L.head
    pre = L.head
    
    # Start pointer t at the head of list A (auxiliary list)
    t = A.head

    # Outer loop runs n times, where n is the number of elements to process
    for _ in range(n):
        # Inner loop moves p forward until cnt reaches m
        while cnt < m:
            # Move p to the next node
            p = p.next
            
            # Move pre to the next node only if cnt > 0 to avoid moving it on the first iteration
            if cnt > 0:
                pre = pre.next
            
            # If p points to a node with data == None, skip this node by moving both p and pre forward
            if p.data == None:
                p = p.next
                pre = pre.next
            
            # Increment the step counter
            cnt += 1
        
        # Add the current node pointed by p to the auxiliary list A
        t.next = p
        t = p
        
        # Remove the current node from list L by adjusting the 'next' pointer of pre
        pre.next = pre.next.next
        
        # Reset the counter for the next iteration
        cnt = 0
    
    # Make the auxiliary list A circular by setting its last node's 'next' to point to its head
    t.next = A.head

if __name__ == "__main__":
    # Create an instance of CLinkList and populate it with values [1, 2, 3, 4, 5, 6]
    L = CLinkList()
    L.CreateListR([1, 2, 3, 4, 5, 6])
    
    # Create an auxiliary CLinkList A
    A = CLinkList()
    
    # Set parameters n (number of elements to process) and m (step count)
    n = 6
    m = 5
    
    # Solve the Josephus problem using lists L and A
    solve_joseph(L, A, n, m)
    
    # Display the contents of the auxiliary list A (which contains removed elements)
    A.display()